package com.interview.javabasic.Algorithm;/*
@李子宁
Happy,happy everyday!
冲鸭！
*/

import com.interview.javabasic.JUC.A;

import java.util.Arrays;

public class Kruskal {
    private int edgeNum;//边的个数
    private char[] vertexs;//顶点数组的个数
    private int[][] matrix;//邻接矩阵
    //使用INF表示两个顶点不能联通
    private static final int INF = Integer.MAX_VALUE;
    public static void main(String[] args) {
        char[] vertex = {'A','B','C','D','E','F','G'};
        int[][] matrix = {
                {0,12,INF,INF,INF,16,14},
                {12,0,10,INF,INF,7,INF},
                {INF,10,0,3,5,6,INF},
                {INF,INF,3,0,4,INF,INF},
                {INF,INF,5,4,0,2,8},
                {16,7,6,INF,2,0,9},
                {14,INF,INF,INF,8,9,0}
        };
        //创建kruskal对象的实例;
        Kruskal kruskal = new Kruskal(vertex, matrix);
        kruskal.print();
        System.out.println("边："+ Arrays.toString(kruskal.getEdges()));
        EData[] edges = kruskal.getEdges();
        kruskal.sortEdegs(edges);
        System.out.println("排序后："+Arrays.toString(edges));
        kruskal.kruskal();

    }
    //构造器
    public Kruskal(char[] vertexs,int[][] matrix){
        //初始化顶点数和边的个数
        int vlen = vertexs.length;
        //初始haunt顶点
        this.vertexs = new char[vlen];
        for (int i = 0; i < vertexs.length; i++) {
            this.vertexs[i] = vertexs[i];
        }
        //初始化边
        this.matrix = new int[vlen][vlen];
        for (int i = 0; i < vlen; i++) {
            for (int j = 0; j < vlen; j++) {
                this.matrix[i][j] = matrix[i][j];
            }
        }
        //统计边
        for (int i = 0; i < vlen; i++) {
            for (int j = i+1; j < vlen; j++) {
                if (this.matrix[i][j]!=INF){
                    edgeNum++;
                }
            }
        }
    }

    public void kruskal(){
        int index = 0;//表示最后数组的索引
        int[] ends = new int[edgeNum];//用于保存已有最小生成树中的每个顶点在最小生成树的终点
        //创建结果数组。
        EData[] res = new EData[edgeNum];
        //获取图中所有的边的集合
        EData[] edges = getEdges();
        System.out.println("图的边的集合="+ Arrays.toString(edges));

        sortEdegs(edges);
        //遍历edegs，数组，判断是否成回路，如果没有，则放入，否则不能
        for (int i = 0; i < edgeNum; i++) {
            int p1 = getPosition(edges[i].start);
            int p2 = getPosition(edges[i].end);
            //获取p1这个顶点在已有的最小生成树的终点
            int m = getEnd(ends,p1);
            int n = getEnd(ends,p2);
            if (m!=n){//没有构成回路
                ends[m] = n;
                res[index++] = edges[i]; // 有一条边加入
                }
        }
        System.out.println("最小生成树为="+Arrays.toString(res));
    }

    //打印邻接矩阵
    public void print(){
        System.out.println("邻接矩阵为：");
        for (int i = 0; i < vertexs.length; i++) {
            for (int j = 0; j < vertexs.length; j++) {
                System.out.printf("%12d",matrix[i][j]);
            }
            System.out.println();
        }
    }

    //对边排序，冒泡排序
    private void sortEdegs(EData[] edges){
        for (int i = 0; i < edges.length - 1; i++) {
            for (int j = 0; j < edges.length - 1 - i; j++) {
                if (edges[j].weight > edges[j+1].weight){
                    EData tmp = edges[j];
                    edges[j] = edges[j+1];
                    edges[j+1] = tmp;
                }
            }
        }
    }
    //传入顶点返回下标
    private int getPosition(char ch){
        for (int i = 0; i < vertexs.length; i++) {
            if (vertexs[i] == ch){
                return i;
            }
        }
        return -1;
    }
    //获取图中的边，放入到数组中，后面需要遍历该数组。
    private EData[] getEdges(){
        int index = 0;
        EData[] edges = new EData[edgeNum];
        for (int i = 0; i < vertexs.length; i++) {
            for (int j = i+1; j < vertexs.length; j++) {
                if (matrix[i][j]!=INF){
                   edges[index++] = new EData(vertexs[i],vertexs[j],matrix[i][j]);
                }
            }
        }
        return edges;
    }
//用于判断两个顶点的终点是否相同,终点是动态生成的，
    private int getEnd(int[] ends,int i){
        while (ends[i] != 0){
            i = ends[i];
        }
        return i;
    }
}

//创建一个类EData,对象实例表示的是一条边
class EData{
    char start;
    char end;
    int weight;
    public EData(char start,char end,int weight){
        this.start = start;
        this.end = end;
        this.weight = weight;
    }
    //重写toString，便于输出边

    @Override
    public String toString() {
        return "EData{" +
                "<" + start +
                "," + end +
                ">=" + weight +
                '}';
    }
}